\documentclass[12pt,a4paper]{article} 

\usepackage{ctex} % 中文支持
\usepackage[top=2.5cm, bottom=2.5cm, left=2.5cm, right=2.5cm]{geometry} % 页边距
\usepackage{amsmath, amssymb} % 数学公式与符号
\usepackage{graphicx}
\usepackage{pythonhighlight}
\usepackage{url} 

\usepackage{longtable} % 表格超过一页

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage{titling}
\setlength{\droptitle}{-2cm} % 标题上移

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% 使用Tikz
\usepackage{tikz}
\usetikzlibrary{graphs}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% 给数字或字母加圆圈
\newcommand*\mycirc[1]{%
   \begin{tikzpicture}
     \node[draw, circle, inner sep=0pt] {#1};
   \end{tikzpicture}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 插入python代码
\usepackage{listings}
\usepackage{color}

% 设置列表的样式
\definecolor{codegreen}{rgb}{0,0.6,0}
\definecolor{codegray}{rgb}{0.5,0.5,0.5}
\definecolor{codepurple}{rgb}{0.58,0,0.82}
\definecolor{backcolour}{rgb}{0.95,0.95,0.92}

\lstdefinestyle{mystyle}{
    backgroundcolor=\color{backcolour},   
    commentstyle=\color{codegreen},
    keywordstyle=\color{magenta},
    numberstyle=\tiny\color{codegray},
    stringstyle=\color{codepurple},
    basicstyle=\ttfamily\footnotesize,
    breakatwhitespace=false,         
    breaklines=true,                 
    captionpos=b,                    
    keepspaces=true,                 
    numbers=left,                    
    numbersep=5pt,                  
    showspaces=false,                
    showstringspaces=false,
    showtabs=false,                  
    tabsize=2
}

\lstset{style=mystyle}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%文档的题目、作者与日期
\author{五六七 }
\title{比赛项目排序与旅行商问题 }

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}

\maketitle

\begin{abstract}
安排比赛项目的顺序，使得运动员尽可能不需要连续参加比赛。
\end{abstract}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\setcounter{tocdepth}{2}
%\renewcommand\contentsname{目录}
%
%\renewcommand {\baselinestretch} {1.3}\normalsize 
%\tableofcontents 
%\renewcommand {\baselinestretch} {1.0}\normalsize


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{问题描述}
在一场运动会中，同一个运动员可能会报名不同的比赛项目。
如何安排比赛的次序，使得运动员尽量不需要连续参加两个项目。已知运动员的报名表如下。

\begin{longtable}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\caption{运动会报名表} \\ \hline
项目		&1	&2	&3	&4	&5	&6	&7	&8	&9	&10	&11	&12	&13	&14	 \\ \hline 
\endfirsthead

\multicolumn{15}{r}{{\small 表 \thetable\ 续上页}} \\ \hline
项目		&1	&2	&3	&4	&5	&6	&7	&8	&9	&10	&11	&12	&13	&14	 \\ \hline 
\endhead

\hline
\multicolumn{15}{r}{{\small 续下页}} \\
\endfoot

\hline
\endlastfoot

% 表格数据

运动员1 	&	&*	&*	&	&	&	&	&	&*	&	&	&	&*	&	 \\ \hline 
运动员2 	&	&	&	&	&	&	&	&*	&	&	&*	&*	&	&	 \\ \hline 
运动员3 	&	&*	&	&*	&	&	&	&	&	&*	&	&	&	&	 \\ \hline 
运动员4 	&*	&	&*	&	&	&	&	&*	&	&	&	&*	&	&	 \\ \hline 
运动员5 	&	&	&	&	&	&	&	&	&	&	&*	&	&*	&*	 \\ \hline 
运动员6 	&	&	&	&	&*	&*	&	&	&	&	&	&	&	&	 \\ \hline 
运动员7 	&	&	&	&	&	&	&	&	&	&	&	&*	&*	&	 \\ \hline 
运动员8 	&	&	&	&	&	&	&	&	&	&*	&	&	&	&*	 \\ \hline 
运动员9 	&	&*	&	&*	&	&	&	&	&	&*	&*	&	&	&	 \\ \hline 
运动员10 	&*	&*	&	&*	&	&	&*	&	&	&	&	&	&	&	 \\ \hline 
运动员11 	&	&*	&	&*	&	&	&	&	&	&	&	&	&*	&*	 \\ \hline 
运动员12 	&	&	&	&	&	&	&	&*	&	&*	&	&	&	&	 \\ \hline 
运动员13 	&	&	&	&	&*	&	&	&	&	&*	&	&	&	&*	 \\ \hline 
运动员14 	&	&	&*	&*	&	&	&	&*	&	&	&	&	&	&	 \\ \hline 
运动员15 	&	&	&*	&	&	&	&	&*	&	&	&	&*	&	&	 \\ \hline 
运动员16 	&	&	&	&	&	&	&	&	&*	&	&*	&*	&	&	 \\ \hline 
运动员17 	&	&	&	&	&	&*	&	&	&	&	&	&	&	&*	 \\ \hline 
运动员18 	&	&	&	&	&	&	&*	&	&	&	&	&*	&	&	 \\ \hline 
运动员19 	&	&	&*	&	&	&	&	&	&	&*	&	&	&	&	 \\ \hline 
运动员20 	&*	&	&*	&	&	&	&	&	&	&	&	&	&	&	 \\ \hline 
运动员21 	&	&	&	&	&	&	&	&*	&	&	&	&	&	&*	 \\ \hline 
运动员22 	&	&*	&	&	&*	&	&	&	&	&	&	&	&	&	 \\ \hline 
运动员23 	&	&	&	&	&	&	&*	&	&	&	&	&*	&	&	 \\ \hline 
运动员24 	&	&	&	&	&	&	&*	&*	&	&	&	&	&*	&*	 \\ \hline 
运动员25 	&*	&*	&	&	&	&	&	&	&	&*	&	&	&	&	 \\ \hline 
运动员26 	&	&	&*	&	&*	&	&	&	&	&	&	&	&	&*	 \\ \hline 
运动员27 	&	&	&	&	&	&*	&	&	&	&	&*	&	&	&	 \\ \hline 
运动员28 	&	&*	&	&	&	&	&	&*	&	&	&	&	&	&	 \\ \hline 
运动员29 	&*	&	&	&	&	&	&	&	&	&	&*	&*	&	&	 \\ \hline 
运动员30 	&	&	&	&*	&*	&	&	&	&	&	&	&	&	&	 \\ \hline 
运动员31 	&	&	&	&	&	&*	&	&*	&	&	&	&*	&	&	 \\ \hline 
运动员32 	&	&	&	&	&	&	&*	&	&	&*	&	&	&	&	 \\ \hline 
运动员33 	&	&	&	&*	&	&*	&	&	&	&	&	&	&	&	 \\ \hline 
运动员34 	&*	&	&*	&	&	&	&	&	&	&	&	&	&*	&*	 \\ \hline 
运动员35 	&	&	&	&*	&*	&	&	&	&	&	&	&*	&	&	 \\ \hline 
运动员36 	&	&	&	&*	&	&	&*	&	&	&	&	&	&	&	 \\ \hline 
运动员37 	&*	&	&	&	&	&	&	&	&*	&*	&	&	&	&	 \\ \hline 
运动员38 	&	&	&	&	&	&*	&	&*	&	&*	&	&	&	&*	 \\ \hline 
运动员39 	&	&	&	&	&*	&	&	&*	&*	&	&	&	&*	&	 \\ \hline 
运动员40 	&	&	&	&	&	&*	&*	&	&*	&	&	&	&*	&	 \\ \hline 

\end{longtable}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{建立模型}

\subsection{转化为旅行商问题}

问题的结果是项目 $1,2,3,\cdots,14$ 的一个次序。
考虑一个图，其中每个顶点代表一个项目，而两个顶点之间的距离是同时参加这两个项目的运动员的人数。
那么本题就转化为在这个图中，寻找一条路径，恰好不重复也不遗漏地经过了每个顶点，
而且使得这条路径的总距离为最小。这就是旅行商问题。

为计算与编程，先考虑一个简单的情况，一个只有项目1-3的图。
\begin{center}
\begin{tikzpicture}[auto]

\node [circle,draw] (s1) at (0,0) {1}; 
\node [circle,draw] (s2) at (3,0) {2}; 
\node [circle,draw] (s3) at (3,-2) {3}; 

\draw (s1) to node {2} node [swap]{} (s2);
\draw (s1) to node {} node [swap]{5} (s3);
\draw (s2) to node {1} node [swap]{} (s3);

\end{tikzpicture}
\end{center}

设矩阵 $A$ 是上述14个顶点的邻接矩阵。即这个矩阵的第 $(i,j)$ 元素为同时参加项目 $i$ 与项目 $j$ 的人数。
为计算这个矩阵，先将上述表格保存为一个40乘14的矩阵$B$. 
然后计算矩阵 $B$ 的第$i$个列向量与第$j$ 个列向量的内积。这个数字正好是同时参加这两个项目的人数。
计算可得下述矩阵，其中对角线元素 $a_{ii}$ 表示第 $i$ 个项目共有多少人参加，
非对角线元素 $a_{ij}$ 表示同时参加项目 $i$ 与项目 $j$ 的人数。

\begin{eqnarray}
%A=\begin{pmatrix}
A=\left[ 
\begin{array}{cccccccccccccc}
7&  3&  2&  1&  0&  0&  1&  1&  1&  2&  1&  2&  1&  2  \\ 
3&  9&  1&  4&  1&  0&  1&  2&  1&  3&  1&  1&  2&  2  \\ 
2&  1&  7&  1&  0&  0&  1&  2&  1&  1&  0&  1&  2&  1  \\ 
1&  4&  1&  8&  2&  1&  1&  1&  0&  2&  1&  1&  1&  1  \\ 
0&  1&  0&  2&  7&  1&  0&  1&  1&  1&  0&  1&  1&  2  \\ 
0&  0&  0&  1&  1&  7&  1&  2&  1&  1&  1&  1&  1&  1  \\ 
1&  1&  1&  1&  0&  1&  7&  1&  1&  1&  0&  2&  2&  1  \\ 
1&  2&  2&  1&  1&  2&  1& 11&  1&  2&  1&  4&  2&  2  \\ 
1&  1&  1&  0&  1&  1&  1&  1&  5&  1&  1&  1&  3&  0  \\ 
2&  3&  1&  2&  1&  1&  1&  2&  1& 10&  1&  0&  0&  3  \\ 
1&  1&  0&  1&  0&  1&  0&  1&  1&  1&  6&  3&  1&  1  \\ 
2&  1&  1&  1&  1&  1&  2&  4&  1&  0&  3& 10&  1&  0  \\ 
1&  2&  2&  1&  1&  1&  2&  2&  3&  0&  1&  1&  8&  4  \\ 
2&  2&  1&  1&  2&  1&  1&  2&  0&  3&  1&  0&  4& 10  \\ 
\end{array}
\right].
%\end{pmatrix}
\end{eqnarray}

\subsection{使用随机搜索求解旅行商问题}
思路就是不停测试各种可能的路径，记录测试到的最短的路径长度。

\subsection{使用0-1整数规划求解旅行商问题}
一条路径可以由只取0或1的整数变量 $x_{ij}$ 确定，其中
\begin{eqnarray}
x_{ij}=\left\{\begin{array}{ll}
1, & \text{当该路径经过从i到j的边，} \\
0, & \text{当该路径不经过从i到j的边。} \\
\end{array}\right.
\end{eqnarray}
因为 $i,j$ 的取值范围都是1-14，即14个顶点的编号，所以这里一共有 $14^2=196$ 个变量。

设邻接矩阵 $A$ 的元素为 $a_{ij}$, 即报名参加第$i,j$个项目的运动员有 $a_{ij}$ 个。则目标函数是 
\begin{eqnarray}
\text{minimize }\,\, z = \sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} a_{ij}x_{ij}. 
\end{eqnarray}

约束条件是矩阵 $X=(x_{ij})$ 的每一行正好有一个1，其余都是0，而且每一列也正好只有一个0，其余都是0. 
这正好是矩阵 $X$ 的行列式的展开里的某一项。例如路径
 \begin{eqnarray}
2\to 1\to 4 \to 3 \to 6\to 5 \to 8 \to 7 \to 14 \to 13 \to 12 \to 11\to 10 \to 9 
\end{eqnarray}
可由下述矩阵表示， 

\begin{eqnarray}
X=\left[ 
\begin{array}{cccccccccccccc}
0&\mycirc{1}&0&0&0&0&0&0&0&0&0&0&0&0 \\ 
\mycirc{1}&0&0&0&0&0&0&0&0&0&0&0&0&0 \\ 
0&0&0&\mycirc{1}&0&0&0&0&0&0&0&0&0&0 \\ 
0&0&\mycirc{1}&0&0&0&0&0&0&0&0&0&0&0 \\ 
0&0&0&0&0&\mycirc{1}&0&0&0&0&0&0&0&0 \\ 
0&0&0&0&\mycirc{1}&0&0&0&0&0&0&0&0&0 \\ 
0&0&0&0&0&0&0&\mycirc{1}&0&0&0&0&0&0 \\ 
0&0&0&0&0&0&\mycirc{1}&0&0&0&0&0&0&0 \\ 
0&0&0&0&0&0&0&0&0&0&0&0&0&\mycirc{1} \\ 
0&0&0&0&0&0&0&0&0&0&0&0&\mycirc{1}&0 \\ 
0&0&0&0&0&0&0&0&0&0&0&\mycirc{1}&0&0 \\ 
0&0&0&0&0&0&0&0&0&0&\mycirc{1}&0&0&0 \\ 
0&0&0&0&0&0&0&0&0&\mycirc{1}&0&0&0&0 \\ 
0&0&0&0&0&0&0&0&\mycirc{1}&0&0&0&0&0 \\ 
\end{array}
\right].
\end{eqnarray}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{编程计算}

\subsection{使用随机搜索}

%\begin{python}
\begin{lstlisting}[language=Python]
mydata=np.genfromtxt('sports_enrollment.csv',delimiter=',')

# 去掉第一行项目编号、第一列运动员编号
A=mydata[1:,1:]

#将nan转化为零
B=np.nan_to_num(A)

#计算邻接矩阵
C=B.T
D=C@B

#保存为整数型
F=np.zeros([14,14],dtype=int)
for k in range(14):
    for m in range(14):
        F[k,m]=int(D[k,m])

#随机搜索法
BestR=np.array(range(14))
BestS=100
for t in range(200000):
    R=np.random.permutation(14)
    S=0
    for k in range(13):
        S=S+F[R[k],R[k+1]]
    if S<BestS:
        BestS=S
        BestR=R
print(BestR)
print(BestS)

\end{lstlisting}
%\end{python}


\subsection{使用TSP算法}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{回答问题}

经过一番随机搜索，找到比赛项目次序
 \begin{eqnarray}
4\to 3\to 5\to 7, 11\to 2\to 6\to 13\to 10\to 12\to 14\to 9\to 1\to 8, 
\end{eqnarray}
其中有5人次要连续参加比赛。


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\section{参考文献 }
\begin{thebibliography}{99}
\bibitem{sishoukui-2} 司守奎,孙玺菁. \emph{Python数学建模算法与应用}, 国防工业出版社. 2022年1月第1版. 


\end{thebibliography}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\begin{table}[ht]\centering
\caption{运动会报名表1-25 }\vspace{0.2cm}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline 
项目		&1	&2	&3	&4	&5	&6	&7	&8	&9	&10	&11	&12	&13	&14	 \\ \hline 
运动员1 	&	&*	&*	&	&	&	&	&	&*	&	&	&	&*	&	 \\ \hline 
运动员2 	&	&	&	&	&	&	&	&*	&	&	&*	&*	&	&	 \\ \hline 
运动员3 	&	&*	&	&*	&	&	&	&	&	&*	&	&	&	&	 \\ \hline 
运动员4 	&*	&	&*	&	&	&	&	&*	&	&	&	&*	&	&	 \\ \hline 
运动员5 	&	&	&	&	&	&	&	&	&	&	&*	&	&*	&*	 \\ \hline 
运动员6 	&	&	&	&	&*	&*	&	&	&	&	&	&	&	&	 \\ \hline 
运动员7 	&	&	&	&	&	&	&	&	&	&	&	&*	&*	&	 \\ \hline 
运动员8 	&	&	&	&	&	&	&	&	&	&*	&	&	&	&*	 \\ \hline 
运动员9 	&	&*	&	&*	&	&	&	&	&	&*	&*	&	&	&	 \\ \hline 
运动员10 	&*	&*	&	&*	&	&	&*	&	&	&	&	&	&	&	 \\ \hline 
运动员11 	&	&*	&	&*	&	&	&	&	&	&	&	&	&*	&*	 \\ \hline 
运动员12 	&	&	&	&	&	&	&	&*	&	&*	&	&	&	&	 \\ \hline 
运动员13 	&	&	&	&	&*	&	&	&	&	&*	&	&	&	&*	 \\ \hline 
运动员14 	&	&	&*	&*	&	&	&	&*	&	&	&	&	&	&	 \\ \hline 
运动员15 	&	&	&*	&	&	&	&	&*	&	&	&	&*	&	&	 \\ \hline 
运动员16 	&	&	&	&	&	&	&	&	&*	&	&*	&*	&	&	 \\ \hline 
运动员17 	&	&	&	&	&	&*	&	&	&	&	&	&	&	&*	 \\ \hline 
运动员18 	&	&	&	&	&	&	&*	&	&	&	&	&*	&	&	 \\ \hline 
运动员19 	&	&	&*	&	&	&	&	&	&	&*	&	&	&	&	 \\ \hline 
运动员20 	&*	&	&*	&	&	&	&	&	&	&	&	&	&	&	 \\ \hline 
运动员21 	&	&	&	&	&	&	&	&*	&	&	&	&	&	&*	 \\ \hline 
运动员22 	&	&*	&	&	&*	&	&	&	&	&	&	&	&	&	 \\ \hline 
运动员23 	&	&	&	&	&	&	&*	&	&	&	&	&*	&	&	 \\ \hline 
运动员24 	&	&	&	&	&	&	&*	&*	&	&	&	&	&*	&*	 \\ \hline 
运动员25 	&*	&*	&	&	&	&	&	&	&	&*	&	&	&	&	 \\ \hline 
\end{tabular}
\end{table}



\begin{table}[ht]\centering
\caption{运动会报名表26-40 }\vspace{0.2cm}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline 
项目		&1	&2	&3	&4	&5	&6	&7	&8	&9	&10	&11	&12	&13	&14	 \\ \hline 
运动员26 	&	&	&*	&	&*	&	&	&	&	&	&	&	&	&*	 \\ \hline 
运动员27 	&	&	&	&	&	&*	&	&	&	&	&*	&	&	&	 \\ \hline 
运动员28 	&	&*	&	&	&	&	&	&*	&	&	&	&	&	&	 \\ \hline 
运动员29 	&*	&	&	&	&	&	&	&	&	&	&*	&*	&	&	 \\ \hline 
运动员30 	&	&	&	&*	&*	&	&	&	&	&	&	&	&	&	 \\ \hline 
运动员31 	&	&	&	&	&	&*	&	&*	&	&	&	&*	&	&	 \\ \hline 
运动员32 	&	&	&	&	&	&	&*	&	&	&*	&	&	&	&	 \\ \hline 
运动员33 	&	&	&	&*	&	&*	&	&	&	&	&	&	&	&	 \\ \hline 
运动员34 	&*	&	&*	&	&	&	&	&	&	&	&	&	&*	&*	 \\ \hline 
运动员35 	&	&	&	&*	&*	&	&	&	&	&	&	&*	&	&	 \\ \hline 
运动员36 	&	&	&	&*	&	&	&*	&	&	&	&	&	&	&	 \\ \hline 
运动员37 	&*	&	&	&	&	&	&	&	&*	&*	&	&	&	&	 \\ \hline 
运动员38 	&	&	&	&	&	&*	&	&*	&	&*	&	&	&	&*	 \\ \hline 
运动员39 	&	&	&	&	&*	&	&	&*	&*	&	&	&	&*	&	 \\ \hline 
运动员40 	&	&	&	&	&	&*	&*	&	&*	&	&	&	&*	&	 \\ \hline 
\end{tabular}
\end{table}

